The Complexity of Checkers on an N x N Board
Josephine Nyoike, Elizabeth Carney, Prayasha Chaudhary, Maddy Fox
4/30/2019
Introduction
Definition: PSPACE-hard: a problem that can be decided by a Turing Machine using polynomial space.
The regular game of checkers is a two-player board game played on an 8 x 8 checkerboard, where pieces jump diagonally to take away all of the opponent’s pieces. Each player begins the game with 12 pieces and each of those pieces becomes a king once it reaches the opposite end. Becoming a king allows the players to move forward and backward, further aiding the players to conquer the opponent’s pieces.
This game of checkers consists of slightly different rules. In our game, there are no size constraints, allowing us to work with an NxN board, where N is an integer. Our theory focuses on end-game problems, where all the positions constructed are either forced wins for Black or forced wins for White and a draw can never result under best play. We also only focused on the center pieces in order to disregard any constraints imposed by the relationship between board size and maximum number of pieces. And of those centerpieces, all are kings, so can move forward and backwards.
The main objective of this paper was to prove if a forced win from any arbitrary position on an NxN checkers board is PSPACE-Hard and/or PSPACE-Complete.
We consider the following question first:
Q0 : Given an arbitrary position, can a White king jump all of Black’s checkers in a single move?
Q0 is solvable in polynomial time if it is restricted to positions on the NxN board. Build an algorithm that determines whether a White King can force a win and apply it to each of the White’s Kings in turn.
Proof:
Observe that when we have a fixed White king as the would-be jumber, we reduce the number of jumpable squares to ½ and visitable squares to ¼. For instance: assuming that the White King is at \(A(i,j)\) such that this is the square that is on the intersection of row i and column j, the number of visitable squares from A are the squares \((h,k)\) such that \((h-i)+(k-j)=0\) and the jumpable squares are those that are diagonally adjacent to visitable squares.
Algorithm:
Given a position involving only kings and a square A that is occupied by a White king:
- Remove the White King and mark a Black King as “eligible” i.e. it is on a square jumpable from A.
- If none is eligible, then a White King cannot jump all of Black’s checkers in a single move.
- Define a graph such that:
- vertices are the unoccupied visitable squares from A
- there is an edge for every Black king connecting the unique two visitable squares diagonally adjacent to the piece.
- vertices are the unoccupied visitable squares from A
From this algorithm it is clear that a White king can jump all of Black’s pieces in one single move if and only if G contains a path starting at A that traverses every edge exactly once. We, however, observe that this is Euler’s path problem which is solvable in \(O(n)\) where n is the number of edges. We will then consider a different question.
Claim
Q1 : Given an arbitrary position, does Black(White) have a forced win from that position?
The main result is that Q1 is always PSACE-hard even when the position only involves kings i.e. it is solvable in polynomial space if and only if every problem that is solvable in polynomial space can also be solved in polynomial time. Additionally, if the drawing rule that a game is drawn whenever there occurs a sequence N^3 moves for both players is applied, Q1 is PSPACE-complete.
Proof
In order to prove that this problem is PSPACE-hard, we will simulate a different known PSPACE-hard problem within the context of a game of checkers. After the simulation’s outcome is decided, it will be translated into either “winning” or “losing” the game. Thus, we must have a systematic way for either Black or White to force a win. This is harder than it might sound for checkers, because the pieces’ positions matter much more than the sheer number of pieces; all of a player’s pieces can be captured in a single move if they are positioned vulnerably.
So, the authors construct a “phalanx” formation in order to guarantee that one side will win. In this example, Black forces a win and White loses. The \((n, m, k)\) phalanx consists of an interior area of m rows and m columns, occupied by n White kings. Surrounding the interior is an area completely filled with Black kings, which measures 4n rows by 4n columns. There must be at least k Black kings on the interior perimeter as shown on the image below. Then, those kings can gradually move inward, decreasing the diameter of the interior area, until all of the White kings have either been captured or rendered immobile. No matter the dimensions of the gameboard, Black will win, because the outer sea of Black kings is deep enough to shrink White’s territory by induction.
Next, the authors create a nested-phalanx setup where either Black or White could force a win. The known PSPACE-hard problem (Bipartite Planar Geography) is simulated in the center of the board, surrounded by a potential phalanx of Black kings with a gap in one side. If Black kings filled in that gap, the formation would be a full phalanx and would guarantee Black’s victory. However, the gap acts as a pathway for a line of White kings that extends from the center (where the simulation is taking place) past the Black formation and leads to a potential phalanx of White kings in the form of a lengthy spiral that wraps around the interior many times. If some White kings moved up diagonally, their formation would become a series of nested squares or “picket lines,” which is equivalent to a \((n, m, k)\) phalanx as illustrated in the image below, and White would win.
The final outcome depends on a “dangerous king.” If Black’s dangerous king escapes, it could capture all of White’s kings in a single move, jumping the entire spiral and forcing a win. However, if White can prevent it from escaping, then White kings can transform their spiral into picket lines and create their own phalanx, winning the game. The total number of checkers needed for this construction is polynomial and dependent on how many pieces are involved in the known PSPACE-hard problem.
In order to prove that forcing a win from an arbitrary start position is PSPACE-Complete, we need to compare it to a PSPACE-hard problem. The paper actually uses a PSPACE-Complete problem, called BIPARTITE PLANAR GEOGRAPHY (which I will abbreviate from here on out as BPG). As you might guess from the name, BPG is a two player game of sorts played on a bipartite, planar graph. This means no edges cross over each other, and the vertices can be grouped into two sets, V1 and V2, such that no vertices in V1 are connected to any other vertices in V1 and no vertices in V2 are connected to any other vertices in V2. The graph is further restricted in that there must be one vertex, v0, with in-degree 0 and out-degree 1, and then all the other nodes must have one of the following four (in degree, out-degree) pairings of (1,0), (1,1), (1,2), or (2,1). Then, to actually play the game, each player is assigned either V1 or V2 as their node set to work on, and the two players take turns drawing arcs from one node in their set to another. Player 1’s first arc must leave v0, and each arc (other than the first one drawn) must start at the vertex that the previous arc ended at. The first person who cannot draw any more arcs within the constraints of the rules loses. The figure below is an example of what a BPG game in progress might look like. 
To transform BPG to NxN Checkers, there are a few steps to take. First, the vertices in BPG get mapped to squares on the checkerboard. Then, the arcs from BPG are replaced by “jumpable paths” on the checkerboard, with the other player’s checkers in the squares that are jumped. A jumpable path is a path that zig-zags diagonally back and forth jumping over a line of checkers of the opposite color of whichever piece is doing the jumping, as illustrated in the figures below.
To start the game, player 1 moves the checker on the square that corresponds with v0 along the arc to the next vertex, call it v1. Then, player 2 makes a move that corresponds to a path from v1 to some other vertex (in the opposite bipartite set as v1). The game continues like this with the players alternating turns until one player is out of possible paths to take. At this point, the player either launches the dangerous king (if they are playing Black) or ambushes the dangerous king (if they are playing White) and forces a win for themself. Note, the different in and out degrees of the vertices in BPG correspond to characteristics of the jumpable paths in NxN Checkers. For instance, a vertex with in degree 1 and out degree 2 corresponds to a path where you only have one option of where to start from, but at some point in jumping down the path, you get to choose between two possible paths to continue on. A figure depicting an example path for each (in-degree, out-degree) pairing is included below.
This transformation process simply involves looping through all the vertices in the BPG graph, looping through the vertices in the opposite bipartite set, checking if there is an edge between the two vertices, and if so, creating a jumpable path on the board. If n is the number of vertices in the graph, this process takes n2 steps, which is polynomial time. So, Black has a forced win in NxN Checker if and only if player 1 has a forced win in the Planar Bipartite Geography, and the same holds for White and player 1. Also, it takes a polynomial amount of time to transform from NxN Checkers to the Planar Bipartite Geography. So, checkers is PSPACE-hard, also and PSPACE-complete if you include the rule where you stop the game and call it a draw after N3 turns.
Our Assessment + Conclusion + Shortcomings and Areas for Future Improvement
The main result of this paper is that NxN Checkers is PSPACE-hard, and can be PSPACE-complete if you include the rule where you stop the game and call it a draw after N3 turns. We also found that it is possible for White to jump all of Black’s pieces if and only if there is an Euler path in the graph described in the proof of Q0.
One obvious shortcoming of these results is that neither is very applicable to your average game of checkers. Realistically, nobody playing checkers is going to actually set up a phalanx or a spiral that changes into picket lines. Additionally, these results are under the assumption that all pieces are kings, which isn’t always the case in a normal game of checkers. It would be interesting to see how the results would change if only some or none of the pieces were kings. Finally, while many of the images in the paper are great and helpful, others are less than clear. For instance Figure 2, shown below, is not very self-explanatory, and the paragraph in the paper where it is discussed didn’t really help us interpret it either. 
Individual Team Member Contributions
Maddy worked on understanding and summarizing the reduction between BPG and NxN Checkers (Section 3 of the paper). Prayasha and Josephine were responsible for dissecting the layout of the proof, understanding draw situations and establishing the rules of this particular game. (Section 1 of the paper).Elizabeth worked on the translation from the proven PSPACE-hard problem to a game of checkers, and how the construction of the nested potential phalanxes could allow either player to force a win (Section 2 of the paper). Each of us worked on the same general topics on both the website and the slides.